Recent developments in the field of computer aided modeling enable designers to manipulate representations of physical objects that have been scanned into a computer using lasers. The representation is often a two-dimensional (2-D) surface (i.e., a 2-dimensional manifold) embedded in three-dimensional (3-D) Euclidean space. The surface is constructed by collecting laser range information from various viewing angles and combining it to reconstruct the surface of the object. Initially, this surface is represented in unparameterized form. For example, a common unparameterized surface representation is a dense, seamless polygon mesh, i.e., a collection of polygons joined at their edges. This polygon mesh model of the physical object often then forms the basis for subsequent manipulation and animation. A typical model generated from 75 scans of a physical object using a laser range scanner might contain on the order of 350,000 polygons.
Dense polygon meshes are an adequate representation for some applications such as stereolithographic manufacturing or computer renderings. However, for a number of other application domains, smooth, parameterized surface representations are required in order to permit useful editing and manipulation of the surface. By smooth or parameterized surfaces we mean surfaces whose mathematical representation has a higher order mathematical property such as the existence of a global analytical derivative. In contrast to smooth surface representations, polygonal meshes are just a set of connected planar facets; they do not posses an analytical derivative.
Smooth surface representations offer useful advantages over an irregular polygonal mesh representation. Some of these advantages are:
Smooth appearance: Several applications such as consumer product design require for aesthetic reasons that 3-D surface models possess a smooth appearance. Polygonal meshes cannot be used in these applications because they may appear faceted (unless the polygons are made extremely small, which increases the expense of processing and storing the model). PA1 Compact representation: A smooth surface representation can usually represent complex surface shapes more efficiently than polygonal meshes. PA1 Flexible control: Smooth surface representations usually offer an easier interface to design, control and modify surface geometry and texture. PA1 Mathematical differentiability: Several applications use computational procedures that require the surface to be everywhere differentiable or curvature continuous (e.g., finite element analysis). For such applications, polygonal meshes cannot be used because they are merely piecewise linear surfaces. PA1 Manufacturability: Some manufacturing procedures such as CNC milling require a smooth surface representation to create high quality results. PA1 Hierarchical modeling: Creating manipulable hierarchies from smooth surfaces is a significantly simpler task than doing the same with dense, irregular, polygonal meshes. PA1 1. Controlled parameterization PA1 2. Controlled surface approximation based on the parameterization PA1 1. Feature curve that rigidly guides the parameterization (feature curves) PA1 2. Feature curve that loosely guides the parameterization (flow curves) PA1 3. User-defined feature curve PA1 4. Automatically generated feature curve PA1 1. Output surface type PA1 2. User defined fidelity of the approximation to the entire parameterized data set (global fidelity) PA1 3. User defined fidelity of the approximation within specific regions of the surface (local fidelity) PA1 4. Automatic setting of global fidelity PA1 5. Automatic setting of local fidelity PA1 1. Noise distributed over the entire surface of the mesh. PA1 2. Local blemishes such as pittings or undesirable creases in specific areas of the mesh.
Examples of smooth surfaces include parametric representations such as NURBS, B-spline and Bezier surfaces, implicit representations such as spheres and cylinders, algebraic representations based on explicit equations, and so on. To satisfy users that prefer or require smooth surface representations, techniques are needed for creating and fitting smooth surfaces to dense polygonal meshes.
Known techniques for creating and fitting smooth surfaces to polygon meshes, however, consist of a single-step parameterized fit that creates a fixed "ideal" parameterization with a fixed "ideal" surface approximation having that parameterization. Because the parameterization and fit are created simultaneously in one step, the user has limited control over the properties of the parameterization and the properties of the fit. Since having flexibility and control over surface parameterization and fit is crucial for most applications, improved and more flexible techniques for fitting smooth surfaces to polygon meshes are needed.